C++ STL使用技巧

string

string类是在C语言字符串处理的整体封装，C语言中使用char类型的数组实现对于字符串的处理，但是其有很多缺点，因此在C++中引入了对于char *的封装，就是string类。

string类的常用API列在下方备查：

//string类的初始化
//只定义了str，值为空字符串
string str;
//将str初始化为n大小的字符串，指定值为n个c
string str(n, 'c');
//用str2来初始化
string str(str2);
//用char *来赋值和初始化
char *p = "hello world!";
string str = p;
string str2(p);
//直接给出值
string str = "hello world!";
//大小，返回的是string::size_type类型，其实是unsigned
str.size();

//stringstream用于将某一个string定向到输入
stringstream ssin(str);
while (ssin >> s);

//字符串常用比较函数
#include <cctype>
isalnum(c); //字母或数字时为真
isalpha(c); //字母为真
isdigit(c); //数字为真
islower(c); //小写字母为真
isuppper(c); //大写字母为真
char t = tolower(c); //如果是大写字母，输出对应小写字母
char t = toupper(c); //如果是小写字母，输出对应大写字母

//范围for，引用可以修改c
for (auto &c : str)
    c = toupper(c);

vector

vector在C++中是作为动态数组存在的，当需要使用数组但是又无法确定数组大小的时候，可以使用vector。同时vector也可以作为线性容器来存储数据。

另外vector内元素因为是不定长的，因此需要随时增加vector的最大可容纳范围。每次使用倍增的思想添加元素，当元素到了最大上限时，最大上限多开辟一倍的大小。

不要在for循环中添加和删除元素，否则迭代器会出现问题，改变了大小，begin和end位置也会有问题。

vector的常用API在下方备查：

//vector中元素可以是类，但引用不是对象，因此不能是引用
vector<stack<int>> f;
vector<Sales_item> f;
//初始化vector，大小为n，默认赋值
vector<int> f(n);
//初始化vector，大小为n, 赋值为0
vector<int> f(n, 0);
//初始化vector，初始化列表
vector<int> f = {1, 2, 3, 4};
vector<int> f{1, 2, 3, 4};
//二维vector的初始化，大小为n + 1,即可以使用下标为0~n
vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
//返回大小
f.size();
//在最后加入一个数
f.push_back(1);
//删除最后一个元素
f.pop_back();
//对vector进行排序，其中f.begin()和f.end()是迭代器
sort(f.begin(), f.end());
//vector支持的所有迭代器
//begin是指向第一个元素的迭代器，end是指向最后一个元素后边那个位置的迭代器，空的情况下begin和end是同一位置，都是尾后迭代器
//rbegin是指向右数第一个元素的迭代器，rbegin + 1 = end
//rend是指第一个元素之前的一个位置
f.begin();
f.end();
f.rbegin();
f.rend();
//vector对象赋值和对象比较
f1 = f2; //将f2中所有对象拷贝替换f1内元素
f1 == f2; //相等的含义是：元素数量相等且对应位置的所有元素值相等
f1 <, <=, >, >= f2 //字典顺序进行比较

//迭代器操作
*iter; //返回迭代器所指元素的引用
iter -> mem; //解引用iter并获取该元素的mem成员，等价于(*iter).mem

//reserve是直接开辟多大的空间，但是其中不放元素
f.reserve(4);
//这里size是0
f.size();
//这里是最大容量，因为开了4所以是4，如果满了再加一个，就变成了8（双倍开辟）
f.capacity();

list

list事实上是双向链表，相比于vector可以实现O(1)的删除操作，但是无法实现随机访问。

list<int> link;
link.push_back(1);
link.push_front();
link.pop_back();
link.begin();
link.end();
link.rbegin();
link.front();
link.back();
link.size();
auto it = link.begin();
link.erase(it);
link.erase(it, it + 5);

map和set的区别以及底层实现

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。

map和set区别在于：

  1. map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。
  2. set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。
  3. map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

红黑树简介

红黑树是什么

首先红黑树和AVL树一样，是一种二叉搜索树。可以在log(n)的时间复杂度下查找某一元素，插入和删除某一元素。AVL树通过旋转保持严格的平衡（左右子树高度差不大于1），而红黑树通过控制树中节点的颜色和拓扑结构，保持不存在任何一条从根到叶子节点的路径是另外一条路径的两倍。因此相比于红黑水，AVL树的旋转次数会更多，红黑树用非严格的平衡来换取更少的旋转次数。这样，其最坏的二分查找（二叉搜索树的查找原理）时间复杂度不会退化为O(n)。

红黑树的定义

  1. 每一个节点都是红色或者黑色。
  2. 根是黑色的。
  3. 所有叶子节点（没有子节点的点，或者空都算叶子）都是黑色的。
  4. 每个红色节点必须有两个黑色的子节点。（所有路径不会出现连续的红色节点）
  5. 从给定节点到其后代叶子节点的每一条路径都包含相同数量的黑色节点，且没有一条路径会是别的路径长度的两倍（推论性质）。

红黑树的左旋和右旋

要完成红黑树的添加与删除，又不予以上的五条性质有冲突，每一次插入或者删除，都要重新编排和着色。为了要保证不破坏二叉树原有的大的数在左，小的数在右的性质。 那么任意移动位置显然是不行的，所以很多操作都由左旋和右旋进行代替了。

红黑树通过节点颜色来判断何时进行何种旋转，通过旋转来保持整颗树的性质不变。具体变换有很多种分类讨论，因为是简介，所以不一一列举。

知乎.听说你还不懂什么是红黑树？

Blog.红黑树原理和算法介绍

赏

庄敬日强，功不唐捐。